package com.code.test.dance;

/**
 * https://leetcode.cn/problems/trapping-rain-water/description/
 * <p>
 * <p>
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * <p>
 * <p>
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 * 示例 2：
 * <p>
 * 输入：height = [4,2,0,3,2,5]
 * 输出：9
 * <p>
 * <p>
 * 提示：
 * <p>
 * n == height.length
 * 1 <= n <= 2 * 104
 * 0 <= height[i] <= 105
 */
public class Water {

    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};

        System.out.println(water(nums));
    }

    /**
     * 双数组法
     */
    public static int waterOn(int[] height) {

        int len = height.length;
        if (len < 2) {
            return 0;
        }
        int[] maxLeft = new int[len];
        int[] maxRight = new int[len];

        int ret = 0;

        maxLeft[0] = height[0];
        for (int i = 1; i < len; i++) {
            //跟左边的比
            maxLeft[i] = Math.max(maxLeft[i - 1], height[i]);
        }

        maxRight[len - 1] = height[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            //跟右边的比
            maxRight[i] = Math.max(maxRight[i + 1], height[i]);
        }
        /**
         * 上面的效果是
         * 左边：如果左边比较大，会放在当前，每个都是
         * 右边：如果右边比较大，会放在当前[i],如果自己比较大，就是自己
         */

        for (int i = 1; i < len - 1; i++) {
            int count = Math.min(maxLeft[i], maxRight[i]) - height[i];
            if (count > 0) {
                ret += count;
            }
        }
        return ret;

    }

    /**
     * 暴力解法
     */
    public static int water(int[] height) {

        int water = 0;
        /**
         * water[i] = min(
         *  max(0,i-1),
         *  max(i+1,height.length-1)
         * )
         */

        int len = height.length;
        //遍历所有柱子
        //头尾是不用算的，边上没有柱子可以构成凹槽
        for (int i = 1; i < len - 1; i++) {
            //当前柱子
            int curH = height[i];
            //看左边柱子
            int leftH = 0;
            /**
             * 如果不算自己，假设是1，2，3，算出来是min(1,3)-2，构成是没有凹槽的，但是变成了1-2
             * 如果算了自己,min(2,3)-2 = 0，即没有凹槽，无法接水
             */
            for (int j = 0; j <= i; j++) {
                int curLeftH = height[j];
                leftH = Math.max(curLeftH, leftH);
            }
            int rightH = 0;
            for (int k = i; k < len; k++) {
                int curRightH = height[k];
                rightH = Math.max(curRightH, rightH);
            }
            if (Math.min(leftH, rightH) - curH < 0) {
                System.out.println(leftH + ":" + rightH + ":" + curH);
            } else {
                //左右高度最小，减去当前柱子高度，差值即为可以装的水
                water += Math.min(leftH, rightH) - curH;
            }

        }

        return water;
    }
}
